package com.mgq.algorithm.forcerecursive;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

/**
 * @author MaGuangQi
 * 打印所有子序列
 * 比如 abc
 * 每个字符都可以选择要,或者选择不要
 * 最后结果是 abc,ab,ac,a,bc,b,c ''
 *                       O
 *                   要a/ \不要a
 *                    O   O
 *                要b/ \不要b
 *                O    O
 *            要c/ \xc要c/ \不要c
 * @date 2022-01-06 15:08
 **/
public class PrintAllSubSequence {
    public static void main(String[] args) {
       // process(new char[]{'a', 'b', 'c'}, 0, new ArrayList<>());
        process2(new char[]{'a', 'b', 'c'}, 0);
    }
    /**
     *
     * @param str 字符集合
     * @param i i表示来到i位置,有2个选择,可以选择要,或者不要
     * @param res 过程中保存的结果
     */
    public static void process(char[] str, int i, List<Character> res) {
        //表示走完了
        if (i == str.length) {
            printList(res);
            return;
        }
        List<Character> newList=copyList(res);
        res.add(str[i]);
        //i处字符不要
        process(str,i+1,newList);
        //要i处字符
        process(str,i+1,res);
    }

    /**
     * 解法二: 更省空间
     * @param str
     * @param i
     */
    public static void process2(char[] str, int i) {
        if (i == str.length) {
            System.out.println(Arrays.toString(str));
            return;
        }
        char tmp=str[i];
        str[i]=0; //ascii码 0是空字符null
        process2(str,i+1); //不要当前字符的路
        str[i]=tmp;
        process2(str,i+1);//要当前字符的路

    }
    private static List<Character> copyList(List<Character> res) {
        List<Character> list = new ArrayList<>(res.size());
        list.addAll(res);
        return list;
    }

    private static void printList(List<Character> res) {
        for (Character re : res) {
            System.out.print(re+"___");
        }
        System.out.println();
    }
}
